package Stack_04.PolandNotation_04;

/*
 * @Author 罗
 * @date 2020/3/14 - 10:58 下午
 *
 */

import Stack_04.calculate_03.StackForCalculator;
import org.junit.Test;

import java.util.*;

public class Translate_02 {

    @Test
    public void test(){
        String infixExpression = " 100.2  +( ( \f \n 2\t + 3)  *4)-55.1    ";
        double result = calculateAll(infixExpression);
        System.out.println("计算结果是 "+ result);
    }

    /**
     * 封装
     * 1.普通表达式(不带空格)，转为中缀表达式List
     * 2.再转为后缀表达式List，后缀表达式List计算
     * 3.得出计算结果
     *
     *
     * 完整版逆波兰计算器：
     * (1)支持+ - * / ()
     * (2)支持多位数，double
     * (3)兼容处理，过滤任何空白字符，包括 空格、制表符\t、换页符\f、换行符\n
     * @param infixExpression
     * @return
     */
    public static double calculateAll(String infixExpression){
//        去除表达式中多余的空白字符，包括 空格、制表符\t、换页符\f、换行符\n
        infixExpression = infixExpression.replace(" ","");
        infixExpression = infixExpression.replace("\t","");
        infixExpression = infixExpression.replace("\n","");
        infixExpression = infixExpression.replace("\f","");

        String infixExpressionWithoutSpace = addSpaceForInfixExpression(infixExpression);
        System.out.println("原中缀表达式\t"+infixExpression + "\n中缀表达式添加空格后\t" + infixExpressionWithoutSpace);

        List<String> infixExpressionList = SuffixExpression_01.getListString(infixExpressionWithoutSpace);

        System.out.println("遍历中缀表达式，手动加空格");
        for (String s : infixExpressionList) {
            System.out.print(s+" ");
        }
        List<String> suffixExpressionList = parse(infixExpressionList);
        System.out.println("\n遍历后缀表达式，手动加空格");
        for (String s : suffixExpressionList) {
            System.out.print(s+" ");
        }
        System.out.println();
        return SuffixExpression_01.calculate(suffixExpressionList);

    }

    /**
     * 中缀表达式转后缀表达式的思路分析
     * 1.初始化两个栈：运算栈s1和存储中间结果栈s2
     * 2.从左至右扫描中缀表达式
     * 3.遇到操作数时，将其压入中间结果栈s2
     * 4.遇到运算符时，比较其与s1栈顶运算符的优先级
     *      4.1 如果s1为空，或栈顶运算符为左括号"("，则直接将此运算符入栈
     *      4.2 否则，若优先级比栈顶运算符高，也将运算符压入s1
     *              如果s1栈顶运算符为"("，新加进来的运算符为"+"
     *              则将"+"直接压入s1，因为"("不是运算符，只是用来调整优先级
     *              不对：而且在StackForCalculator.priority()中 "(,)"的优先级被设置为了-1
     *              我在这里单独设置了判断栈顶已经是"("方法
     *                  所以"+"优先级比栈顶的"("高
     *      4.3 否则，将s1栈顶的运算符弹出pop()并压入到s2中，再次转到
     *              (4.1)与s1中新的栈顶运算符相比较
     * 5.遇到括号时
     *      5.1 如果是左括号"("，则直接压入s1
     *      5.2 如果是右括号")"，则依次弹出s1栈顶的运算符，并压入s2
     *              直到遇到左括号"("为止，此时将这一对括号丢弃
     * 6.重复步骤2-5,直到中缀表达式的最右边
     * 7.将s1中剩余的运算符依次弹出并压入s2
     * 8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
     * @Version 3.0
     * @param infixExpressionList
     * @return
     */
    public static List<String> parse(List<String> infixExpressionList){
        Stack <String> s1 = new Stack<>();
        List <String> s2 = new ArrayList<>();
        String item;
        for (int i = 0; i < infixExpressionList.size(); i++) {
            item = infixExpressionList.get(i);
            if(  item.matches("^(-?\\d+)(\\.\\d+)?$")){
//                是数字（直接匹配浮点数的正则表达式）-->直接加入s2
                s2.add(item);
            }else{
//                是运算符
                if( item.contentEquals("(")){
                    s1.push(item);
                }else if( item.contentEquals(")")){
                    while( ! s1.peek().contentEquals("(")){
                        s2.add(s1.pop());
                    }
//                    将左括号弹出
                    s1.pop();
                }else {
                    while ( ! s1.isEmpty() &&
                            StackForCalculator.priority(item.charAt(0)) <= StackForCalculator.priority(s1.peek().charAt(0))) {
                    /*不满足4.2(若优先级比栈顶运算符高)----->满足4.3(优先级 <= 栈顶运算符优先级)，但是要附加s1非空判断
                      这样做的目的是避免判断4.2的麻烦，如果栈顶已经是"("但是"("又没有优先级，需要单独判断，通过这里的转换，就不用这么麻烦了
                        每次往s1添加运算符都要经过本方法，s1中的运算符相当于是优先级生序排列的
                        若s1中某段优先级为 7,8,9  而新打算加入的优先级为5，则需要把7,8,9 优先级的操作符都弹出，并加入到s2
                            而我之前自己写的方法(Version 1.0 和 Version 2.0)只将优先级为9的运算符弹出，
                            就把优先级为5的运算符加入了，最终s1的结果是7,8,5 错误
                        这里循环只执行了将优先级较高的操作符7,8,9转移到s2
                     */
                        s2.add(s1.pop());
                    }
/*                      还需要把优先级为5的操作符放入s1
                        但是同时也包含了其他情况
                            1.s1栈数据为空，直接将操作符加入s1
                            2.还满足4.2，若优先级比栈顶运算符高，也将运算符压入s1
                            3.若s1栈顶已经是"("这里也满足，直接将本次运算符加入s1就完事了
 */
                        s1.push(item);
                }



            }

        }
        while ( !s1.isEmpty() ){
            s2.add(s1.pop());
        }


        return s2;
    }



    /**
     * @Version 2.0
     * @param infixExpressionList
     * @return
     */
    @Deprecated
    public static List<String> parseInfixExpressionListToSuffixExpressionListByArrayListAndStack(List<String> infixExpressionList){
        Stack<String> s1 = new Stack<>();
        List<String> s2  = new ArrayList<>();
        String unit;
        for (int i = 0; i < infixExpressionList.size(); i++) {
            unit = infixExpressionList.get(i);
            if( ! unit.matches("\\d+")){
//            if(StackForCalculator.isOperation(unit.charAt(0))){
//                为操作符
                while(true) {
                    if (s1.isEmpty() || s1.peek().contentEquals("(")) {
                        s1.push(unit);
                        break;
                    } else if (StackForCalculator.priority(unit.charAt(0)) > StackForCalculator.priority(s1.peek().charAt(0))) {
                        s1.push(unit);
                        break;
                    } else if(unit.contentEquals("(")){
                        s1.push(unit);
                        break;
                    }else if(unit.contentEquals(")")){
                        while (true){
                            String moveSymbol = s1.pop();
                            if(moveSymbol.contentEquals("(")){
                                break;
                            }
                            s2.add(moveSymbol);
                        }
                        break;
                    }else{
                        s2.add(s1.pop());
//                        没有break，跳转while开头
                    }
                }
            }else{
//                为操作数
                s2.add(unit);
            }
        }
//     7.将s1中剩余的运算符依次弹出并压入s2
        while(! s1.isEmpty()){
            s2.add(s1.pop());
        }

/*     8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
            因为是ArrayList，所以不用弹出，直接返回即可
 */

        return s2;
    }


    /**
     * 中缀表达式转后缀表达式的思路分析
     * 1.初始化两个栈：运算栈s1和存储中间结果栈s2
     * 2.从左至右扫描中缀表达式
     * 3.遇到操作数时，将其压入中间结果栈s2
     * 4.遇到运算符时，比较其与s1栈顶运算符的优先级
     *      4.1 如果s1为空，或栈顶运算符为左括号"("，则直接将此运算符入栈
     *      4.2 否则，若优先级比栈顶运算符高，也将运算符压入s1
     *              如果s1栈顶运算符为"("，新加进来的运算符为"+"
     *              则将"+"直接压入s1，因为"("不是运算符，只是用来调整优先级
     *              不对：而且在StackForCalculator.priority()中 "(,)"的优先级被设置为了-1
     *              我在这里单独设置了判断栈顶已经是"("方法
     *                  所以"+"优先级比栈顶的"("高
     *      4.3 否则，将s1栈顶的运算符弹出pop()并压入到s2中，再次转到
     *              (4.1)与s1中新的栈顶运算符相比较
     * 5.遇到括号时
     *      5.1 如果是左括号"("，则直接压入s1
     *      5.2 如果是右括号")"，则依次弹出s1栈顶的运算符，并压入s2
     *              直到遇到左括号"("为止，此时将这一对括号丢弃
     * 6.重复步骤2-5,直到中缀表达式的最右边
     * 7.将s1中剩余的运算符依次弹出并压入s2
     * 8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
     * @param infixExpressionList
     * @return
     */
    @Deprecated
    public static List<String> parseInfixExpressionListToSuffixExpressionList(List<String> infixExpressionList){
        Stack<String> s1 = new Stack<>();//符号栈
        /*
            中间结果栈s2，因为自始至终s2都是只添加内容
            最后取出的时候用的还是逆序（先进后出），没有用到栈的先进先出特性
            所以可以用ArrayList栈代替s2栈
         */
        Stack<String> s2 = new Stack<>();

        String unit = null;
        for (int i = 0; i < infixExpressionList.size(); i++) {
            unit = infixExpressionList.get(i);
            /*
            * 正则表达式：//d+  表示多位整数
            * */
            if(unit.matches("\\d+")){
//                判断不是操作符，与正则表达式等效
//            if( ! StackForCalculator.isOperation(unit.charAt(0))){
//                遇到操作数，直接压入s2
                s2.push(unit);
            }else{
                /*
                 * 遇到操作符，比较和栈顶的优先级
                 *      1.如果s1为空，或者遇到"("则直接压入s1
                 * */
                while (true) {
                    if (s1.isEmpty() || unit.contentEquals("(")) {
                        s1.push(unit);
                        break;
                    } else if (s1.peek().contentEquals("(") || StackForCalculator.priority(unit.charAt(0))
                            > StackForCalculator.priority(s1.peek().charAt(0))) {
                        /*
                         * s1的栈顶为"(" 或者 优先级 比 s1栈顶优先级还高
                         * */
                        s1.push(unit);
                        break;
                    } else if(unit.contentEquals(")")){
                        /*
                        * 是")"的情况
                        * 依次弹出s1栈顶的运算符，并压入s2
                        *              直到遇到左括号"("为止，此时将这一对括号丢弃
                        * */
                        while(true){
                            String s1Content = s1.pop();
                            if(s1Content.contentEquals("(")){
                                break;
                            }
                            s2.push(s1Content);
                        }
                        break;
                    }else{
                        /*
                         * 1.弹出s1栈顶的元素，并且加到s2栈中
                         * */
                        s2.push(s1.pop());
                        /*
                         * 2.再将本元素与s1中的栈顶元素相比较
                         * */
                    }
                }
            }
        }
        /*
         * 已经抵达中缀表达式的最右边
         * 将s1中剩余的运算符依次弹出并压入s2
         *  */
        while (!s1.isEmpty()){
            s2.push(s1.pop());
        }
        /*
        * 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
        * */
        Iterator<String> iterator = s2.iterator();
        List<String> listResult = new ArrayList<>();
        while (iterator.hasNext()){
            listResult.add(iterator.next());
        }
        return listResult;
    }

    /**
     * 为中缀表达式添加空格，以方便转为中缀表达式List
     * @param infixExpression
     * @return
     */
    public static String addSpaceForInfixExpression(String infixExpression){
        char temp;
        StringBuilder buildNumber = new StringBuilder();
        StringBuilder joint = new StringBuilder();

        for (int i = 0; i < infixExpression.length(); i++) {
            temp = infixExpression.charAt(i);
            if( StackForCalculator.isOperation(temp)){
                if(buildNumber.length() > 0){
                    joint.append(buildNumber.append(" "));
                    buildNumber.delete(0,buildNumber.length());
                }
                joint.append(temp).append(" ");
            }else{
                buildNumber.append(temp);
            }
        }
        joint.append(buildNumber);
        return joint.toString();
    }


}


